SherbyNet - /page/wikibook/entry.mu

Micron Document

<!DOCTYPE html>

<title>Nurse scheduling problem</title>

</head>

Nurse scheduling problem

</h1>

</header>

The nurse scheduling problem (NSP), also called the nurse rostering problem (NRP), is the <a href="Operations_research" title="Operations research">operations research</a> problem of finding an optimal way to assign nurses to shifts, typically with a set of <a href="Hard_constraint" class="mw-redirect" title="Hard constraint">hard constraints</a> which all valid solutions must follow, and a set of soft constraints which define the relative quality of valid solutions.<a href="#cite_note-IoannisTassopoulos-1">[1]</a> Solutions to the nurse scheduling problem can be applied to constrained scheduling problems in other fields.<a href="#cite_note-UweAickelin-2">[2]</a><a href="#cite_note-GarethBeddoe-3">[3]</a>

While research on computer-assisted employee scheduling goes back to the 1950s,<a href="#cite_note-Bailey-4">[4]</a> the nurse scheduling problem in its current form was introduced in two parallel publications in 1976.<a href="#cite_note-Miller-5">[5]</a><a href="#cite_note-Warner-6">[6]</a> It is known to have <a href="NP-hard" class="mw-redirect" title="NP-hard">NP-hard</a> complexity.<a href="#cite_note-IoannisTassopoulos-1">[1]</a>

<div class="mw-heading mw-heading2"><h2 id="General_description">General description</h2></div>

Conventionally, hospital nursing is <a href="Shift_work" title="Shift work">shift work</a> that is divided up to provide coverage 24 hours per day, 7 days per week. The hospital has restrictions and requirements for what coverage is needed, and each nurse has their own wishes and restrictions as well. The problem is described as finding a schedule that fulfills the objectives of the hospital and covers all shifts, while respecting as many of the nurses' preferences as possible.

The problem is not unique to nursing. It applies in any other profession or situation where shift coverage must be planned out.

<div class="mw-heading mw-heading2"><h2 id="Constraints">Constraints</h2></div>

Creating a schedule means attempting to satisfy certain constraints on how that schedule is laid out. There are two types of constraint: hard constraints, which must be met for the schedule to be valid; and soft constraints, which are desirable but not mandatory.

Depending on the policies of a hospital, the preferences of individual nurses may be treated as either a soft constraint,<a href="#cite_note-MelissaGoodman-7">[7]</a> or as a hard constraint.<a href="#cite_note-GrahamWinstanley-8">[8]</a>

Hard constraints may include physical limitations or legal requirements. Some examples of possible hard constraints are:

<ul><li>All shifts require nursing coverage.</li>

<li>A nurse cannot work more more than one shift at the same time.</li>

<li>A nurse cannot work more than 24 hours in a day, or more than 7 days in a week.</li>

<li>A nurse must not work more than a legally specified number of days in a row.</li>

<li>A nurse must have a legally specified number of rest hours between shifts.</li>

<li>Any newly licensed nurse must be paired with an experienced nurse.</li>

<li>There must always be one <a href="Charge_nurse" class="mw-redirect" title="Charge nurse">charge nurse</a> on duty.</li>

<li>Certain shifts must be covered by nurses with special qualifications.<a href="#cite_note-9">[9]</a></li></ul>

Soft constraints may be hospital policies or nurse preferences. Some examples of possible soft constraints are:

<ul><li>All nurses should work approximately the same number of weekend shifts.</li>

<li>All nurses should work approximately the same difficulty in shift assignments.</li>

<li>A nurse should not work a day shift and a night shift without a rest day in between.</li>

<li>One nurse prefers to have all their work days in a row, and then have all their days off in a row.</li>

<li>One nurse prefers to work no more than two consecutive days, with a day off in between.</li>

<li>One nurse cannot work Wednesday each week because they have no child care available that day.</li>

<li>Two nurses feel they work well together and prefer to be scheduled to work together.</li></ul>

<div class="mw-heading mw-heading2"><h2 id="Solutions">Solutions</h2></div>

Solutions to the problem use a variety of techniques, including both mathematically exact solutions<a href="#cite_note-MelissaGoodman-7">[7]</a> and a variety of heuristic solutions using <a href="Decomposition_(computer_science)" title="Decomposition (computer science)">decomposition</a>,<a href="#cite_note-RubenLagatie-10">[10]</a> <a href="Parallel_computing" title="Parallel computing">parallel computing</a>,<a href="#cite_note-RubenLagatie-10">[10]</a><a href="#cite_note-BaumeltZdenek-11">[11]</a> <a href="Stochastic_optimization" title="Stochastic optimization">stochastic optimization</a>,<a href="#cite_note-IoannisTassopoulos-1">[1]</a> <a href="Genetic_algorithm" title="Genetic algorithm">genetic algorithms</a>,<a href="#cite_note-MelissaGoodman-7">[7]</a> <a href="Ant_colony_optimization_algorithms" title="Ant colony optimization algorithms">colony optimization</a>,<a href="#cite_note-MelissaGoodman-7">[7]</a> <a href="Simulated_annealing" title="Simulated annealing">simulated annealing</a>,<a href="#cite_note-MelissaGoodman-7">[7]</a> <a href="Quantum_annealing" title="Quantum annealing">quantum annealing</a>,<a href="#cite_note-12">[12]</a> <a href="Tabu_search" title="Tabu search">Tabu search</a>,<a href="#cite_note-MelissaGoodman-7">[7]</a> and <a href="Coordinate_descent" title="Coordinate descent">coordinate descent</a>.<a href="#cite_note-BaumeltZdenek-11">[11]</a><a href="#cite_note-LizzyAugustine-13">[13]</a>

Burke et al. (2004)<a href="#cite_note-EdmundBurke-14">[14]</a> summarised the state of art of academic research to the nurse rostering problem, including brief introductions of various then published solutions.

<ul><li><a href="Assignment_problem" title="Assignment problem">Assignment problem</a></li>

<li><a href="Constraint_programming" title="Constraint programming">Constraint programming</a></li>

<li><a href="Employee_scheduling_software" title="Employee scheduling software">Employee scheduling software</a></li></ul>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}

/* end https://en.wikipedia.org/ */

</style><div class="reflist reflist-columns references-column-width reflist-columns-2">

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><cite id="CITEREFSolosTassopoulosBeligiannis2013" class="citation journal cs1">Solos, Ioannis; Tassopoulos, Ioannis; Beligiannis, Grigorios (21 May 2013). <a rel="nofollow" class="external text" href="https://doi.org/10.3390%2Fa6020278">"A Generic Two-Phase Stochastic Variable Neighborhood Approach for Effectively Solving the Nurse Rostering Problem"</a>. <a href="Algorithms_(journal)" title="Algorithms (journal)">Algorithms</a>. 6 (2): 278–308. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.3390%2Fa6020278">10.3390/a6020278</a>.</cite>

</li>

<cite id="CITEREFAickelinDowsland2004" class="citation journal cs1">Aickelin, Uwe; Dowsland, Kathryn A. (2004). "An Indirect Genetic Algorithm for a Nurse Scheduling Problem". Computers & Operations Research. 31 (5): 761–778. <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<a rel="nofollow" class="external text" href="https://arxiv.org/abs/0803.2969">0803.2969</a>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2Fs0305-0548%2803%2900034-0">10.1016/s0305-0548(03)00034-0</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:8772185">8772185</a>.</cite>

</li>

<li id="cite_note-GarethBeddoe-3"><a href="#cite_ref-GarethBeddoe_3-0">^</a> <cite id="CITEREFBeddoePetrovic2003" class="citation journal cs1">Beddoe, Gareth; Petrovic, Sanja (2003). <a rel="nofollow" class="external text" href="https://web.archive.org/web/20170829183208/https://www.pomsmeetings.org/ConfProceedings/001/Papers/PSC-08.1.pdf">"A novel approach to finding feasible solutions to personnel rostering problems"</a> (PDF). Proceedings of the 14th Annual Conference of the Production and Operation Management Society. Savannah, Georgia: 1–13. Archived from <a rel="nofollow" class="external text" href="http://pomsmeetings.org/ConfProceedings/001/Papers/PSC-08.1.pdf">the original</a> (PDF) on 29 August 2017. Retrieved 20 March 2014.</cite>

</li>

<li id="cite_note-Bailey-4"><a href="#cite_ref-Bailey_4-0">^</a> <cite id="CITEREFBailey1956" class="citation journal cs1">Bailey, Norman T. J. (1956). <a rel="nofollow" class="external text" href="https://academic.oup.com/jrsssc/article-abstract/5/3/146/6862850">"Statistics in Hospital Planning and Design"</a>. Journal of the Royal Statistical Society Series C: Applied Statistics. 5 (3). Oxford University Press: 146–157. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.2307%2F2985416">10.2307/2985416</a>. <a href="JSTOR_(identifier)" class="mw-redirect" title="JSTOR (identifier)">JSTOR</a> <a rel="nofollow" class="external text" href="https://www.jstor.org/stable/2985416">2985416</a>. Retrieved 14 December 2023.</cite>

</li>

<li id="cite_note-Miller-5"><a href="#cite_ref-Miller_5-0">^</a> <cite id="CITEREFMillerPierskallaRath1976" class="citation journal cs1">Miller, Holmes E.; Pierskalla, William P.; Rath, Gustave J. (1976). <a rel="nofollow" class="external text" href="https://pubsonline.informs.org/doi/abs/10.1287/opre.24.5.857">"Nurse Scheduling Using Mathematical Programming"</a>. Operations Research. 24 (5). INFORMS: 857–870. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1287%2Fopre.24.5.857">10.1287/opre.24.5.857</a>. Retrieved 14 December 2023.</cite>

</li>

<li id="cite_note-Warner-6"><a href="#cite_ref-Warner_6-0">^</a> <cite id="CITEREFWarner1976" class="citation journal cs1">Warner, D. Michael (1976). <a rel="nofollow" class="external text" href="https://pubsonline.informs.org/doi/abs/10.1287/opre.24.5.842">"Scheduling Nursing Personnel According to Nursing Preference: A Mathematical Programming Approach"</a>. Operations Research. 24 (5). INFORMS: 842–856. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1287%2Fopre.24.5.842">10.1287/opre.24.5.842</a>. Retrieved 14 December 2023.</cite>

</li>

<li id="cite_note-MelissaGoodman-7">^ <a href="#cite_ref-MelissaGoodman_7-0">a</a> <a href="#cite_ref-MelissaGoodman_7-1">b</a> <a href="#cite_ref-MelissaGoodman_7-2">c</a> <a href="#cite_ref-MelissaGoodman_7-3">d</a> <a href="#cite_ref-MelissaGoodman_7-4">e</a> <a href="#cite_ref-MelissaGoodman_7-5">f</a> <cite id="CITEREFGoodmanDowslandThompson2007" class="citation journal cs1">Goodman, Melissa D.; Dowsland, Kathryn A.; Thompson, Jonathan M. (2007). <a rel="nofollow" class="external text" href="https://link.springer.com/content/pdf/10.1007/s10732-007-9066-7.pdf">"A grasp-knapsack hybrid for a nurse-scheduling problem"</a> (PDF). Journal of Heuristics. 15 (4). Springer: 351–379. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2Fs10732-007-9066-7">10.1007/s10732-007-9066-7</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:8784023">8784023</a>. Retrieved 20 June 2020.</cite>

</li>

<li id="cite_note-GrahamWinstanley-8"><a href="#cite_ref-GrahamWinstanley_8-0">^</a> <cite id="CITEREFWinstanley" class="citation cs2">Winstanley, Graham, <a rel="nofollow" class="external text" href="https://web.archive.org/web/20140320215801/http://www.cem.brighton.ac.uk/research/cig/papers/SWAT.pdf">A hybrid approach to staff scheduling: The Staff Work Allocation Tool (SWAT)</a> (PDF), Brighton: <a href="University_of_Brighton" title="University of Brighton">University of Brighton</a> School of Computing, Engineering and Mathematics, pp. 1–12, archived from <a rel="nofollow" class="external text" href="http://www.cem.brighton.ac.uk/research/cig/papers/SWAT.pdf">the original</a> (PDF) on 20 March 2014, retrieved 20 March 2014</cite>

</li>

<cite id="CITEREFAickelinWhite2004" class="citation journal cs1">Aickelin, Uwe; White, Paul (2004). "Building Better Nurse Scheduling Algorithms". <a href="Annals_of_Operations_Research" title="Annals of Operations Research">Annals of Operations Research</a>. 128 (1–4): 159–177. <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<a rel="nofollow" class="external text" href="https://arxiv.org/abs/0803.2967">0803.2967</a>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1023%2Fb%3Aanor.0000019103.31340.a6">10.1023/b:anor.0000019103.31340.a6</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:14983974">14983974</a>.</cite>

</li>

<li id="cite_note-RubenLagatie-10">^ <a href="#cite_ref-RubenLagatie_10-0">a</a> <a href="#cite_ref-RubenLagatie_10-1">b</a> <cite id="CITEREFLagatieHaspeslaghDe_Causmaecker2009" class="citation cs2">Lagatie, Ruben; Haspeslagh, Stefaan; De Causmaecker, Patrick (2009), <a rel="nofollow" class="external text" href="https://web.archive.org/web/20160304190332/http://wwwis.win.tue.nl/bnaic2009/papers/junk/bnaic2009_submission_41.pdf">Negotiation Protocols for Distributed Nurse Rostering</a> (PDF), <a href="Eindhoven_University_of_Technology" title="Eindhoven University of Technology">Eindhoven University of Technology</a> Department of Computer Science, archived from <a rel="nofollow" class="external text" href="http://wwwis.win.tue.nl/bnaic2009/papers/junk/bnaic2009_submission_41.pdf">the original</a> (PDF) on 4 March 2016, retrieved 14 February 2014</cite>

</li>

<li id="cite_note-BaumeltZdenek-11">^ <a href="#cite_ref-BaumeltZdenek_11-0">a</a> <a href="#cite_ref-BaumeltZdenek_11-1">b</a> <cite id="CITEREFBäumeltDvořákŠůchaHanzálek2016" class="citation journal cs1">Bäumelt, Zdeněk; Dvořák, Jan; Šůcha, Přemysl; Hanzálek, Zdeněk (2016). "A Novel Approach for Nurse Rerostering based on a Parallel Algorithm". <a href="European_Journal_of_Operational_Research" title="European Journal of Operational Research">European Journal of Operational Research</a>. 251 (2). Elsevier: 624–639. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2Fj.ejor.2015.11.022">10.1016/j.ejor.2015.11.022</a>.</cite>

</li>

<li id="cite_note-12"><a href="#cite_ref-12">^</a> <cite id="CITEREFHumbleNakamuraIkeda2019" class="citation journal cs1">Humble, Travis S.; Nakamura, Yuma; Ikeda, Kazuki (2019-04-27). <a rel="nofollow" class="external text" href="https://www.ncbi.nlm.nih.gov/pmc/articles/PMC6731278">"Application of Quantum Annealing to Nurse Scheduling Problem"</a>. Scientific Reports. 9 (1): 12837. <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<a rel="nofollow" class="external text" href="https://arxiv.org/abs/1904.12139">1904.12139</a>. <a href="Bibcode_(identifier)" class="mw-redirect" title="Bibcode (identifier)">Bibcode</a>:<a rel="nofollow" class="external text" href="https://ui.adsabs.harvard.edu/abs/2019NatSR...912837I">2019NatSR...912837I</a>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1038%2Fs41598-019-49172-3">10.1038/s41598-019-49172-3</a>. <a href="PMC_(identifier)" class="mw-redirect" title="PMC (identifier)">PMC</a> <a rel="nofollow" class="external text" href="https://www.ncbi.nlm.nih.gov/pmc/articles/PMC6731278">6731278</a>. <a href="PMID_(identifier)" class="mw-redirect" title="PMID (identifier)">PMID</a> <a rel="nofollow" class="external text" href="https://pubmed.ncbi.nlm.nih.gov/31492936">31492936</a>.</cite>

</li>

<li id="cite_note-LizzyAugustine-13"><a href="#cite_ref-LizzyAugustine_13-0">^</a> <cite id="CITEREFAugustineFaerKavountzisPatel2009" class="citation cs2">Augustine, Lizzy; Faer, Morgan; Kavountzis, Andreas; Patel, Reema (15 December 2009), <a rel="nofollow" class="external text" href="http://www.math.cmu.edu/~af1p/Teaching/OR2/Projects/P23/ORProject_Final_Copy.pdf">A Brief Study of the Nurse Scheduling Problem (NSP)</a> (PDF), Pittsburgh: <a href="Carnegie_Mellon_School_of_Computer_Science" title="Carnegie Mellon School of Computer Science">Carnegie Mellon School of Computer Science</a>, pp. 1–11, retrieved 20 March 2014</cite>

</li>

<li id="cite_note-EdmundBurke-14"><a href="#cite_ref-EdmundBurke_14-0">^</a> <cite id="CITEREFBurkeDe_CausmaeckerBergheVan_Landeghem2004" class="citation journal cs1">Burke, Edmund; De Causmaecker, Patrick; Berghe, Greet Vanden; Van Landeghem, Hendrik (2004). <a rel="nofollow" class="external text" href="https://lirias.kuleuven.be/bitstream/123456789/123829/1/JOS_">"The state of the art of nurse rostering"</a>. Journal of Scheduling. 7 (6): 441–499. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1023%2FB%3AJOSH.0000046076.75950.0b">10.1023/B:JOSH.0000046076.75950.0b</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:10537343">10537343</a>. Retrieved 10 January 2016.</cite>

</li>

</ol></div>

<div class="mw-heading mw-heading2"><h2 id="External_links">External links</h2></div>

<ul><li><a rel="nofollow" class="external text" href="https://web.archive.org/web/20120206032112/http://www.lania.mx/~ccoello/EMOO/jan00.ps.gz">A study on how to solve the NSP using CGA</a> at the <a href="Wayback_Machine" title="Wayback Machine">Wayback Machine</a> (archived February 6, 2012)</li>

<li><a rel="nofollow" class="external text" href="https://www.mjc2.com/staff-planning-complexity.htm">Why is Scheduling People Hard?</a></li>

<li><a rel="nofollow" class="external text" href="https://www.nurse-scheduling-software.com/">A free solver for nurse scheduling problem</a></li></ul></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2025-08-02" href="https://en.wikipedia.org/wiki/?title=Nurse_scheduling_problem&oldid=1303784469">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>